Technology and Market Trends
The evolution of the telecommunications in general and of the packet switching networks in particular is driven by many factors among which two of them worth emphasizing: technologies and applications.
Communication technologies have realized these last years considerable progress with:
The maturing of new transmission media and specially of optical fiber. High speed rates can now be sustained with very low bit error rates. PA1 The universal use of digital technologies within private and public telecommunications networks. PA1 improving old applications, PA1 optimizing communication networks, PA1 doing new applications. PA1 a very large flexibility to support a wide range of connectivity options, PA1 a very high throughput and a very short packet processing time, PA1 an efficient flow and congestion control. PA1 the flow control for regulating the emitting data rate of the calling subscriber at a rate compatible with what the receiver can absorb. PA1 the load regulation for globally limiting the number of packets present in the network to avoid an overloading of the resources, and PA1 the load balancing for fairly distributing the traffic over all the links of the network to avoid a local congestion in particular resources. PA1 R, the peak bit rate of the incoming traffic in bits per second, PA1 m, the mean bit rate of the incoming traffic in bits per second, and PA1 b, the mean burst duration of the traffic in seconds. PA1 upward if the measurements indicate that either a desired maximum packet loss probability will be exceeded or if the traffic on that connection will start to unfairly interfere with other connections sharing the transmission facilities. PA1 downward if significant bandwidth savings can be realized for both the user of the connection and for the balance of the network, without violating any quality of service guarantees for all of the connections. PA1 measuring the mean bit rate m.sub.n of traffics from said source node, PA1 controlling the flow of said traffics from said source node into the network by means of a leaky bucket control circuit, PA1 measuring the loss probability of packets introduced into said network by said leaky bucket control circuit, PA1 defining adaptation regions on the values of said simultaneous mean bit rate and loss probability measurements, PA1 in response to a pair of said mean bit rate and loss probability measurements falling outside said adaptation regions, modifying the bandwidth allocated to a connection between said source node and said destination node. PA1 wherein said step of defining adaptation regions comprises the step of: PA1 And wherein said step of modifying the bandwidth allocated to the connection comprises the steps of: PA1 increasing the amount of bandwidth .gamma. allocated when: .xi..sub.n &gt;.xi..sub.H PA1 decreasing the amount of bandwidth .gamma. allocated when: .xi..sub.n &lt;.xi..sub.L and m.sub.n &lt;.gamma..
An increase in communication capacity is generating more attractive tariffs and large bandwidths are economically more and more attractive.
On the other hand, in relation with these new emerging technologies, many potential applications that were not possible before are now becoming accessible and attractive. In this environment, three generic requirements are expressed by the users:
High Speed Packet Switching Networks
Data transmission is now evolving with a specific focus on applications and by integrating a fundamental shift in the customer traffic profile. Driven by the growth of workstations, the local area networks interconnection, the distributed processing between workstations and super computers, the new applications and the integration of various and often conflicting structures--hierarchical versus peer to peer, wide versus local area networks, voice versus data--the data profile has become more bandwidth consuming, bursting, non-deterministic and requires more connectivity. Based on the above, there is strong requirement for supporting distributed computing applications across high speed networks that can carry local area network communications, voice, video, and traffic among channel attached hosts, business, engineering workstations, terminals, and small to intermediate file servers. This vision of a high speed multi-protocol network is the driver for the emergence of fast packet switching networks architectures in which data, voice, and video information is digitally encoded, chopped into small packets and transmitted through a common set of nodes and links.
An efficient transport of mixed traffic streams on very high speed lines means for these new network architecture a set of requirements in term of performance and resource consumption which can be summarized as follows:
Connectivity
In high speed networks, the nodes must provide a total connectivity. This includes attachment user's devices, regardless of vendor or protocol, and the ability to have the end user communicate with any other device. The network must support any type of traffic including data, voice, video, fax, graphic or image. Nodes must be able to take advantage of all common carrier facilities and to be adaptable to a plurality of protocols. All needed conversions must be automatic and transparent to the end user.
Throuqhput and Processing Time
One of the key requirement of high speed packet switching networks is to reduce the end-to-end delay in order to satisfy real time delivery constraints and to achieve the necessary high nodal throughput for the transport of voice and video. Increases in link speeds have not been matched by proportionate increases in the processing speeds of communication nodes and the fundamental challenge for high speed networks is to minimize the packet processing time within each node. In order to minimize the processing time and to take full advantage of the high speed/low error rate technologies, most of the transport and control functions provided by the new high bandwidth network architectures are performed on an end-to-end basis. The flow control and particularly the path selection and bandwidth management processes are managed by the access points of the network which reduces both the awareness and the function of the intermediate nodes.
Congestion and Flow Control
Communication networks have at their disposal limited resources to ensure an efficient packets transmission. An efficient bandwidth management is essential to take full advantage of a high speed network. While transmission costs per byte continue to drop year after year, transmission costs are likely to continue to represent the major expense of operating future telecommunication networks as the demand for bandwidth increases. Thus considerable efforts have been spent on designing flow and congestion control processes, bandwidth reservation mechanisms, routing algorithms to manage the network bandwidth.
An ideal network should be able to transmit an useful traffic directly proportional to the traffic offered to the network and as far as the maximum transmission capacity is reached. Beyond this limit, the network should operate at its maximum capacity whatever the demand is. In the reality, the operations diverge from the ideal for a certain number of reasons which are all related to the inefficient allocation of resources in overloaded environment.
For the operation to be satisfactory, the network must be implemented so as to avoid congestion. The simplest solution obviously consists in over-sizing the equipment so as to be positioned in an operating zone which is distant from the congestion. This solution is generally not adopted for evident reasons of costs and it is necessary to apply a certain number of preventive measures among which the main ones are:
Congestion Control
Traffic Characteristics
In order to avoid congestion and insure adequate traffic flow in packet communication networks, it is common to control the access of packet sources to the network on an ongoing basis. In order to successfully control traffic access, it is necessary, first, to accurately characterize the traffic so as to provide appropriate bandwidth for carrying that traffic. Simple measurements which provide accurate estimates of the bandwidth requirements of a source are taught in U.S. Pat. No. 5,274,625 entitled "A Method for Capturing Traffic Behavior with Simple Measurements" (Derby et al.).
In this application, the parameters used to characterize traffic are:
Rather than using the actual burst duration, however, a so-called "exponential substitution" technique is used to calculate an equivalent burst duration which would produce the same packet loss probability if the traffic were a well behaved exponentially distributed on/off process. For traffic widely differing from such an exponential process, this equivalent burst duration produces a much more accurate characterization of the actual traffic and therefore permits a higher density of traffic on the same transmission facilities.
Leaky Bucket
The measured parameters are used to control the access of signal sources to the network when the actual traffic behavior departs significantly from the initial assumptions. A leaky bucket mechanism is one technique for controlling access to the network when the traffic exceeds the initial assumptions, but yet permits transparent access to the network when the traffic remains within these initial assumptions. One such leaky bucket mechanism is shown in U.S. Pat. No. 5,311,513 entitled "Rate-based Congestion Control in Packet Communications Networks" (Ahmadi et al.). More particularly, the leaky bucket mechanism of this application prevents saturation of the network by low priority packets by limiting the number of low priority packets which can be transmitted in a fixed period of time while imposing a minimum on the number of red packets transmitted at a given time. Such leaky bucket control mechanisms optimize the low priority throughput of the packet network. High priority traffic, of course, is transmitted with little or no delay in the leaky bucket mechanism.
Traffic Monitoring
The above-described mechanisms are suitable for controlling traffic only if said traffic is reasonably well-behaved and remains within the general vicinity of the initially assumed traffic parameters. The traffic management system, however, must be structured to deal with traffic which is not well-behaved and which departs substantially from the initially assumed traffic parameters. If such a departure persists for any significant length of time, a new connection bandwidth must be assigned to the connection to accommodate the new traffic parameters. Such adaptation of the control system to radical changes in traffic behavior presents the problems of filtering the traffic measurements to separate transient changes of traffic behavior from longer term changes, and determining reasonable ranges within which the initially assumed traffic parameters can be maintained and outside of which new connection bandwidths must be requested. A bandwidth too large for the actual traffic is wasteful of connection resources while a bandwidth too small results in excessive packet loss. Ancillary problems include reasonable ease in implementation of the adaptation process and reasonable computational requirements in realizing the implementation.
Bandwidth Measurement and Adaptation
U.S. Pat. No. 5,359,593 entitled "Dynamic Bandwidth Estimation and Adaptation for Packet Communication Networks" (Derby et al.) discloses a dynamic adaptation of a traffic control system to changes in the traffic parameters by defining a region within which adaptation is not required and outside of which a new bandwidth allocation must be requested. In particular, the bandwidth requirement is adjusted:
These limits on the adaptation region are converted to values of effective mean burst duration and mean bit rates. The measured effective mean burst duration and mean bit rates are then filtered to insure that the filtered values are statistically reliable, i.e., that a sufficient number of raw measurements are involved to insure a preselected confidence level in the results. This minimum number of raw measurements, in turn, determines the amount of time required to collect the raw measurements, given the mean bit rate of the traffic. This measurement time can be used to measure not only the statistics of the incoming data stream to the leaky bucket, but also the effect of the leaky bucket on the incoming traffic. This latter measurement allows a measure of how well the leaky bucket is dealing with variances in the offered traffic and hence the packet loss probability. When the traffic parameters fall outside of the desired adaptation region, a new connection with a different bandwidth is requested in order to accommodate the changes in the traffic parameters.
The adaptation mechanism disclosed in U.S. Pat. No. 5,359,593 entitled "Dynamic Bandwidth Estimation and Adaptation for Packet Communication Networks" (Derby et al.) insures a continuously reasonable traffic management strategy when the offered traffic variations are small and slow. However, this mechanism presents some limitations when the traffic variations become more important and faster. Then, the adaptation mechanism requires a longer time to converge resulting in an over or under reservation of the bandwidth on the network.
A second limitation of the adaptation mechanism appears when more than one connection is monitored by a single processor which is usually the case in practice. Some connections may require more bandwidth adaptation than other connections within a given time period. The limited processing power of the processor may result in a lack of fairness which might be detrimental to the other connections.